Cài đặt Bellman Thuật_toán_Bellman-Ford

Hàm khởi tạo (bước 0)

Không như khi cài đặt thuật toán Dijkstra, do Bellman chấp nhận cạnh âm, việc sử dụng trị -1 không còn đúng nữa. Tạm thời, ta có thể sử dụng trị MAXINT (32767) cho giá trị inf, vì nếu như chi phí đạt đến ngưỡng này, có thể xem như tràn số.

 step = 0; for {i...} {   mincost[step][i] = inf;   previous[step][i] = i; } mincost[step][x] = 0;

Cài đặt hàm Bellman

Chú ý rằng để có thể kết luận được đồ thị có chu trình âm hay không. ta cần chạy đến bước thứ n (nghĩa là đi qua tối đa n+1 đỉnh). Do đó, cấu trúc dữ liệu để lưu cũng cần lưu ý khi khai báo.

 bSuccess = false; for (step = 1; step <=n; step ++)  // dùng <=n thay vì <n {   for(i...)   {      mincost[step][i] = mincost[step-1][i]      previous[step][i] = previous[step-1][i]      // tìm các đỉnh j có đường nối từ j -->i      // và chi phí bước step-1 của j khác vô cực      for (j...)      if (...&&...)      {         // cập nhật lại nếu chi phí bước step của i là vô cực         // hoặc chi phí đi qua j: mincost[step-1][j]+a[j][i]         //tối ưu hơn         if (...||...)         {            // cập nhật lại chi phí và lưu đỉnh cha         }       }    }    // so sánh mincost[step] với mincost[step-1], nếu bằng nhau    // kết thúc thành công    int bSame = true;    for (i...)    if (mincost[step][i]!= mincost[step-1][i])    {       bSame = false;       break;     // đã giống nhau,đường đi đã tối ưu     if (bSame)        break; }

Cấu trúc dữ liệu

 int mincost [MAX+1][MAX]; int previous[MAX+1][MAX];

Hàm in kết quả

Nếu nStep = n+1, ta kết luận đồ thị có chu trình âm.

Ngược lại, ta sẽ dò chi phí ngược từ bước nStep-1 đến bước 0 (Do bước nStep có giá trị giống bước nStep-1).

 k = y; for (i=nStep-1;i>0;i--)  // chừa lại bước cuối {   printf("%d <---", k);   k = previous[i][k];    // đỉnh trước k } printf("%dn",k);         // có thể thêm kiểm tra k == x